package codingforgreat.class03;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

// 本题测试链接 : https://leetcode.com/problems/freedom-trail/
public class Class07_FreedomTrail {
    public static int findRotateSteps1(String r, String k) {
        char[] ring = r.toCharArray();
        HashMap<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < ring.length; i++) {
            if(!map.containsKey(ring[i])){
                map.put(ring[i], new ArrayList<>());
            }
            map.get(ring[i]).add(i);
        }
        char[] str = k.toCharArray();
        int N = ring.length;
        int M = str.length;
        int[][] dp = new int[N][M + 1];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= M; j++) {
                dp[i][j] = -1;
            }
        }
        return process(0, 0, str, map, N,dp);
    }
    public static int process(int preButton,int index,char[] str,HashMap<Character, List<Integer>> map,int N,int[][] dp){
        if (dp[preButton][index] != -1) {
            return dp[preButton][index];
        }
        if(index == str.length){
            dp[preButton][index] = 0;
            return 0;
        }
        int res = Integer.MAX_VALUE;
        char cur = str[index];
        ArrayList<Integer> nextPositions = (ArrayList<Integer>) map.get(cur);
        for (int next : nextPositions) {
            int cost = dial(preButton, next, N) + 1 + process(next, index + 1, str, map, N,dp);
            res = Math.min(res, cost);
        }
        dp[preButton][index] = res;
        return res;
    }
    public static int dial(int pre,int next,int N){
        return Math.min(Math.abs(pre - next), Math.min(pre, next) + N - Math.max(pre, next));
    }
}
